import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

/*
给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

 */
public class LeetCode_56 {
    public int[][] merge(int[][] arr) {
        Arrays.parallelSort(arr, Comparator.comparingInt(x -> x[0]));

        LinkedList<int[]> list = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            if (list.size() == 0 || list.getLast()[1] < arr[i][0]) {
                list.add(arr[i]);//集合为空，或不满足条件，向后新增
            } else {//满足条件，集合最后元素的end=最大值
                list.getLast()[1] = Math.max(list.getLast()[1], arr[i][1]);
            }
        }
        int[][] res = new int[list.size()][2];//生成结果数组
        int index = 0;
        while (!list.isEmpty()) {//遍历集合
            res[index++] = list.removeFirst();//删除集合首元素
        }
        return res;
    }
}
